package string;

import java.util.*;

/**
 * 139.单词划分
 *
 * @author <a href="zhaoyingling12@163.com">Zhao Simon</a>
 * @description: https://leetcode.cn/problems/word-break/?favorite=2cktkvj 139.单词划分
 * @date 2023/03/13
 **/
public class WordBreak {

    public static void main(String[] args) {
        String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
        List<String> list = new ArrayList<>();
        list.add("a");
        list.add("aa");
        list.add("aaa");
        list.add("aaaa");
        list.add("aaaaa");
        list.add("aaaaaa");
        list.add("aaaaaaa");
        list.add("aaaaaaaa");
        list.add("aaaaaaaaa");
        Solution solution = new Solution();
        System.out.println(solution.wordBreak(s, list));

//        System.out.println("aaa".substring(0, 1));
    }

    static class Solution {
        public boolean wordBreak(String s, List<String> wordDict) {
            if (wordDict == null || wordDict.isEmpty()) {
                return false;
            }
            Set<String> wordSet = new HashSet<>(wordDict);
            return isMatch(s, wordSet, -1);
        }

        private boolean isMatch(String s, Set<String> words, int index) {
            if (index == s.length() - 1) {
                return true;
            }
            boolean[] dp = new boolean[s.length() + 1];
            dp[0] = true;
            for (int i = 1; i <= s.length(); i++) {
                for (int j = 0; j < i; j++) {
                    if (dp[j] && words.contains(s.substring(j, i))) {
                        dp[i] = true;
                    }
                }
            }
            return dp[s.length()];
        }
    }
}
